<script>
  // 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

  // **** 题源：leetcode 19  https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

  // 输入：head = [1,2,3,4,5], n = 2
  // 输出：[1,2,3,5]

  // 输入：head = [1], n = 1
  // 输出：[]

  /**
   * 分析
   * 使用快慢指针 数据结构是链表结构 链条的 如下的一个单链表 有一个next 指向下一个节点
   * p q 定义指针  q 为快指针 p 为慢指针
   * 快指针q 首先使其 与 慢指针p 相隔n个数 也就是删除的数 拿[1,2,3,4,5]举例 q指向4 p指向1
   * 当快指针q 指向null 时 说明 慢指针p.next 指向删除的节点
   * 删除节点 只需要跳过该节点就好了 .next.next
   */

  /**
   * Definition for singly-linked list.
   * function ListNode(val, next) {
   *     this.val = (val===undefined ? 0 : val)
   *     this.next = (next===undefined ? null : next)
   * }
   */
  /**
   * @param {ListNode} head
   * @param {number} n
   * @return {ListNode}
   */

  // 单链表
  function ListNode(val, next) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }

  var removeNthFromEnd = function (head, n) {
    var dummy = new ListNode(0, head); // 创建一个虚拟指针 保证指向 head 的头节点
    var p = dummy; // 慢指针
    var q = dummy; // 快指针
    // 使其和 p q 相隔 n个距离
    for (var i = 0; i < n; i++) {
      q = q.next;
      if (q === null) break; // 说明是头节点 也就是 head只有一个值 next 指向null
    }
    if (!q) return q; // 头节点就返回
    while (q.next) {
      p = p.next;
      q = q.next;
    }
    p.next = p.next.next;
    return dummy.next; // 指向head的头节点 否则会有0包含进去
  };
</script>
